{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Inorder Successor in BST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: inorderSuccessor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树中的中序后继"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵二叉搜索树和其中的一个节点 <code>p</code> ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 <code>null</code> 。</p>\n",
    "\n",
    "<p>节点 <code>p</code> 的后继是值比 <code>p.val</code> 大的节点中键值最小的节点。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/23/285_example_1.PNG\" style=\"height: 117px; width: 122px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,1,3], p = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/23/285_example_2.PNG\" style=\"height: 229px; width: 246px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,3,6,2,4,null,null,1], p = 6\n",
    "<strong>输出：</strong>null\n",
    "<strong>解释：</strong>因为给出的节点没有中序后继，所以答案就返回 <code>null 了。</code>\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 10<sup>4</sup>]</code> 内。</li>\n",
    "\t<li><code>-10<sup>5</sup> <= Node.val <= 10<sup>5</sup></code></li>\n",
    "\t<li>树中各节点的值均保证唯一。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [inorder-successor-in-bst](https://leetcode.cn/problems/inorder-successor-in-bst/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [inorder-successor-in-bst](https://leetcode.cn/problems/inorder-successor-in-bst/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3]\\n1', '[5,3,6,2,4,null,null,1]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        succ = None\n",
    "        if node.right:\n",
    "            succ = node.right\n",
    "            while succ.left:\n",
    "                succ = succ.left\n",
    "            return succ\n",
    "            \n",
    "        pos = node\n",
    "        while pos.parent:\n",
    "            if pos==pos.parent.left:\n",
    "                succ = pos.parent\n",
    "                break\n",
    "            pos = pos.parent\n",
    "        return succ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if not node:\n",
    "            return None\n",
    "        if node.right:\n",
    "            res = node.right\n",
    "            while res.left:\n",
    "                res = res.left\n",
    "            return res\n",
    "        if node.parent and node.parent.left == node:\n",
    "            return node.parent\n",
    "        if node.parent:\n",
    "            res = node.parent\n",
    "            while res.parent and res.parent.right == res:\n",
    "                res = res.parent\n",
    "            if res:\n",
    "                return res.parent\n",
    "            else:\n",
    "                return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if not node:\n",
    "            return None\n",
    "        \n",
    "        if not node.right:\n",
    "            par = node.parent\n",
    "            while par:\n",
    "                if par.val > node.val:\n",
    "                    return par\n",
    "                else:\n",
    "                    par = par.parent\n",
    "            else: return None\n",
    "        \n",
    "        elif not node.right.left:\n",
    "            return node.right\n",
    "        else:\n",
    "            successor = node.right.left\n",
    "            while successor.left:\n",
    "                successor = successor.left\n",
    "            return successor\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if not node:\n",
    "            return None\n",
    "        if node.right:\n",
    "            res = node.right\n",
    "            while res.left:\n",
    "                res = res.left\n",
    "            return res\n",
    "        \n",
    "        \n",
    "        while node.parent and node.parent.right == node:\n",
    "            node = node.parent\n",
    "        return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        succ = None\n",
    "        if node.right:\n",
    "            succ = node.right\n",
    "            while succ.left:\n",
    "                succ = succ.left\n",
    "            return succ\n",
    "\n",
    "        if node.parent is None:\n",
    "            return None\n",
    "        # 有parent，且node.right is None\n",
    "        if node.parent.left == node:\n",
    "            return node.parent\n",
    "        \n",
    "        pos = node\n",
    "        while pos.parent:\n",
    "            if pos==pos.parent.left:\n",
    "                succ = pos.parent\n",
    "                break\n",
    "            pos = pos.parent\n",
    "        return succ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Node':\n",
    "        # 找右子樹第一個\n",
    "        if node.right:\n",
    "            node = node.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        \n",
    "        # 找Parent們中，第一個成為左子樹的，找到後Return Parent\n",
    "        while node.parent and node == node.parent.right:\n",
    "            node = node.parent\n",
    "        return node.parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node.right:\n",
    "            node=node.right\n",
    "            while node.left:\n",
    "                node=node.left\n",
    "            return node\n",
    "        \n",
    "        while node.parent and node.parent.right==node:\n",
    "            node=node.parent\n",
    "        return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node==None:\n",
    "            return None \n",
    "        if node.right != None:\n",
    "            node = node.right\n",
    "            while node.left !=None:\n",
    "                node= node.left \n",
    "            return node \n",
    "        \n",
    "        while node.parent !=None and node.parent.right == node:\n",
    "            node = node.parent\n",
    "        \n",
    "        return node.parent\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        root = node\n",
    "        while root.parent:  root = root.parent\n",
    "        \n",
    "        stack = [None, root]\n",
    "        visited = {}\n",
    "        while True:\n",
    "            cur = stack.pop()\n",
    "            if isinstance(cur, Node):\n",
    "                if cur.right:   stack.append(cur.right)\n",
    "                stack.append(cur.val)\n",
    "                if cur.left:    stack.append(cur.left)\n",
    "                visited[cur.val] = cur\n",
    "            elif cur == node.val:\n",
    "                if isinstance(stack[-1], int):  cur = visited[stack[-1]]\n",
    "                else:   cur = stack[-1]\n",
    "                if not cur or cur.val in visited: return cur\n",
    "                while cur.left: cur = cur.left\n",
    "                return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # 1.当前节点如果有右子树，找右子树的最小节点（最左）\n",
    "        # 2.当前节点没有右子树，向上找第一个大于当前节点的父节点\n",
    "        if node.right:\n",
    "            node = node.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        else:\n",
    "            while node.parent and node.parent.left != node:\n",
    "                node = node.parent\n",
    "            return node.parent\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node.right:\n",
    "            node=node.right\n",
    "            while node.left:\n",
    "                node=node.left\n",
    "            return node\n",
    "        while node.parent and node==node.parent.right:\n",
    "            node=node.parent\n",
    "        return node.parent\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node is None:\n",
    "            return None\n",
    "\n",
    "        if node.right is None:\n",
    "            cur_child = node\n",
    "            iter_p = node.parent\n",
    "            while iter_p is not None and iter_p.right == cur_child:\n",
    "                next_p = iter_p.parent\n",
    "                cur_child = iter_p\n",
    "                iter_p = next_p\n",
    "\n",
    "            if iter_p is None:\n",
    "                return None\n",
    "            return iter_p\n",
    "\n",
    "        right_child = node.right\n",
    "        iter_node = right_child\n",
    "        while iter_node.left is not None:\n",
    "            iter_node = iter_node.left\n",
    "        return iter_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        \n",
    "        # node -> [node+1, ]\n",
    "        # inorder 左 中 右\n",
    "        # 对于当前节点，\n",
    "        # 如果有右子节点 则取值范围应为 [node+1, ] 最小的，即从右子节点从左一撸到底\n",
    "        # 如果他没有右子节点，则要从parent找，找处在 [node+1, parent]最小的\n",
    "\n",
    "        # def dfs(root, upperBound):\n",
    "        #     # 搜索以root为根的子树 [node+1, upperBound] 范围内最小的值\n",
    "\n",
    "        #     if root.val <= node.val:\n",
    "        #         return dfs(root.parent, )\n",
    "        dumbNode = Node(inf)\n",
    "        x = node.val\n",
    "        def dfs(root):\n",
    "            nonlocal x\n",
    "            if root is None:\n",
    "                return None\n",
    "            \n",
    "            if root.val <= x:\n",
    "                return dfs(root.right)\n",
    "            else:\n",
    "                tmp = dfs(root.left)\n",
    "                return tmp if tmp is not None else root \n",
    "\n",
    "\n",
    "        if node.right is not None:\n",
    "            cur = node.right\n",
    "            while cur.left is not None:\n",
    "                cur = cur.left\n",
    "            return cur\n",
    "        else:\n",
    "            cur = node.parent\n",
    "            while cur is not None and cur.val < x:\n",
    "                cur = cur.parent\n",
    "            \n",
    "            # 找cur子树中大于 node 的最小节点\n",
    "            return dfs(cur)\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "        # return dfs(node, inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # 1.当前节点如果有右子树，找右子树的最小节点（最左）\n",
    "        # 2.当前节点没有右子树，向上找第一个大于当前节点的父节点\n",
    "        if node.right:\n",
    "            node = node.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        else:\n",
    "            t = node.val\n",
    "            while node.parent:\n",
    "                node = node.parent\n",
    "                if node.val > t:\n",
    "                    return node\n",
    "            return None\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        p = node.right\n",
    "        while p and p.left:\n",
    "            p = p.left\n",
    "\n",
    "        if p is not None:\n",
    "            return p\n",
    "\n",
    "        p = node\n",
    "        while p.parent and p.parent.right == p:\n",
    "            p = p.parent\n",
    "        \n",
    "        return p.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # 1.当前节点如果有右子树，找右子树的最小节点（最左）\n",
    "        # 2.当前节点没有右子树，向上找第一个大于当前节点的父节点\n",
    "        if node.right:\n",
    "            node = node.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        else:\n",
    "            while node.parent and node.parent.right == node:\n",
    "                node = node.parent\n",
    "            return node.parent\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "\n",
    "\n",
    "        if not node.right:\n",
    "            while node.parent and node == node.parent.right:\n",
    "                node = node.parent\n",
    "            return node.parent\n",
    "        right = node.right\n",
    "        while right.left:\n",
    "            right = right.left\n",
    "        \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\r\n",
    "# Definition for a Node.\r\n",
    "class Node:\r\n",
    "    def __init__(self, val):\r\n",
    "        self.val = val\r\n",
    "        self.left = None\r\n",
    "        self.right = None\r\n",
    "        self.parent = None\r\n",
    "\"\"\"\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Node':\r\n",
    "        if node.right:          #有右子 则是右子树的最左下\r\n",
    "            node = node.right\r\n",
    "            while node.left:\r\n",
    "                node = node.left\r\n",
    "            return node\r\n",
    "        else:\r\n",
    "            while node.parent and node.parent.right == node:\r\n",
    "                node = node.parent\r\n",
    "            return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node.right!=None:\n",
    "            node=node.right\n",
    "            while node.left!=None:\n",
    "                node=node.left\n",
    "            return node\n",
    "        else:\n",
    "            pnode=node.parent\n",
    "            if pnode!=None and pnode.right==node:\n",
    "                while pnode!=None and pnode.right==node:\n",
    "                    node=pnode\n",
    "                    pnode=pnode.parent\n",
    "\n",
    "                return pnode\n",
    "            else:\n",
    "                return pnode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        p = node.right\n",
    "        while p and p.left:\n",
    "            p = p.left\n",
    "        if p:\n",
    "            return p\n",
    "        p = node\n",
    "        while p.parent and p.parent.right == p:\n",
    "            p = p.parent\n",
    "        return p.parent\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # has right ,then right min val\n",
    "        # node is parent left child,then parent\n",
    "        # node is parent right child,then keep finding until node is left child ,return parent \n",
    "\n",
    "        if node.right:\n",
    "            root = node.right\n",
    "            while root.left:\n",
    "                root = root.left\n",
    "            return root \n",
    "        while node.parent and node == node.parent.right:\n",
    "            node = node.parent\n",
    "        return node.parent\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node.right:\n",
    "            root = node.right\n",
    "            while root.left:\n",
    "                root = root.left\n",
    "            return root\n",
    "        else:\n",
    "            while node.parent and node.parent.right == node:\n",
    "                node = node.parent\n",
    "            return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        root = node\n",
    "        while root.parent:  root = root.parent\n",
    "        \n",
    "        stack = [None, root]\n",
    "        visited = {}\n",
    "        while True:\n",
    "            cur = stack.pop()\n",
    "            if isinstance(cur, Node):\n",
    "                if cur.right:   stack.append(cur.right)\n",
    "                stack.append(cur.val)\n",
    "                if cur.left:    stack.append(cur.left)\n",
    "                visited[cur.val] = cur\n",
    "            elif cur == node.val:\n",
    "                if isinstance(stack[-1], int):  cur = visited[stack[-1]]\n",
    "                else:   cur = stack[-1]\n",
    "                if not cur or cur.val in visited: return cur\n",
    "                while cur.left: cur = cur.left\n",
    "                return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        succ = None\n",
    "        if node.right:\n",
    "            succ = node.right\n",
    "            while succ.left:\n",
    "                succ = succ.left\n",
    "            return succ\n",
    "\n",
    "        # if node.parent is None:\n",
    "        #     return None\n",
    "        # 有parent，且node.right is None\n",
    "        # if node.parent.left == node:\n",
    "        #     return node.parent\n",
    "        \n",
    "        pos = node\n",
    "        while pos.parent:\n",
    "            if pos==pos.parent.left:\n",
    "                succ = pos.parent\n",
    "                break\n",
    "            pos = pos.parent\n",
    "        return succ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        root = node\n",
    "        while root.parent:  root = root.parent\n",
    "        \n",
    "        stack = [None, root]\n",
    "        visited = {}\n",
    "        while True:\n",
    "            cur = stack.pop()\n",
    "            if isinstance(cur, Node):\n",
    "                if cur.right:   stack.append(cur.right)\n",
    "                stack.append(cur.val)\n",
    "                if cur.left:    stack.append(cur.left)\n",
    "                visited[cur.val] = cur\n",
    "            elif cur == node.val:\n",
    "                if isinstance(stack[-1], int):  cur = visited[stack[-1]]\n",
    "                else:   cur = stack[-1]\n",
    "                if not cur or cur.val in visited: return cur\n",
    "                while cur.left: cur = cur.left\n",
    "                return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "\n",
    "        # 中序后继 后继的东西\n",
    "        if node.right:\n",
    "            cur = node.right\n",
    "            while cur.left:\n",
    "                cur = cur.left\n",
    "            return cur\n",
    "        else:\n",
    "\n",
    "            while node.parent and node.parent.val < node.val:\n",
    "                node = node.parent\n",
    "            return node.parent\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # 第一种情况，在右下子节点\n",
    "        if node.right:\n",
    "            root = node.right\n",
    "            while root.left:\n",
    "                root = root.left\n",
    "            return root\n",
    "        \n",
    "        # 第二种情况，在上方父节点\n",
    "        while node.parent and node == node.parent.right:\n",
    "            node = node.parent\n",
    "        return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        z = node\n",
    "        root = node\n",
    "        while node: \n",
    "            root = node\n",
    "            node = node.parent\n",
    "        lst = []\n",
    "        def f(o):\n",
    "            if not o: return\n",
    "            f(o.left)\n",
    "            lst.append(o)\n",
    "            f(o.right)\n",
    "        f(root)\n",
    "        for x, y in pairwise(lst):\n",
    "            if x == z: return y\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def DFS(self, node: TreeNode, target: int) -> Optional[TreeNode]:\n",
    "        if node.val == target:\n",
    "            succ: Optional[TreeNode] = None\n",
    "            if node.right is not None:\n",
    "                succ = node.right\n",
    "                while succ.left is not None:\n",
    "                    succ = succ.left\n",
    "            return succ\n",
    "        elif target < node.val:\n",
    "            return self.DFS(node.left, target) or node\n",
    "        else:  # target > node.val\n",
    "            return self.DFS(node.right, target)\n",
    "\n",
    "\n",
    "    def inorderSuccessor(self, root: 'TreeNode', target: 'TreeNode') -> 'TreeNode':\n",
    "        return self.DFS(root, target.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        #目的是找第一个大于p.val的节点。\n",
    "        #很容易想到：我们可以遍历出所有大于p.val的节点\n",
    "        #因为搜索二叉树的性质，我们可以不断缩小搜索范围，迭代性地更新ans的值。\n",
    "        #### 类似推进到极限的原则\n",
    "        ans = None\n",
    "        while root:\n",
    "            if root.val>p.val:\n",
    "                ans = root\n",
    "                root = root.left#收缩上界\n",
    "            else:\n",
    "                root = root.right#收缩下界\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "\n",
    "        self.answer = None\n",
    "        self.find_p = False\n",
    "    \n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if self.answer:\n",
    "                return\n",
    "            \n",
    "            traverse(root.left)\n",
    "\n",
    "            if self.find_p and self.answer == None:\n",
    "                self.answer = root\n",
    "            \n",
    "            if root == p:\n",
    "                self.find_p = True\n",
    "\n",
    "            traverse(root.right)\n",
    "        \n",
    "        traverse(root)\n",
    "        return self.answer\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        self.res = None\n",
    "        self.pre = None\n",
    "\n",
    "        self.inorderTraversal(root, p)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def inorderTraversal(self, root, p):\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        self.inorderTraversal(root.left, p)\n",
    "        if self.pre and self.pre.val == p.val:\n",
    "            self.res = root\n",
    "        self.pre = root\n",
    "        self.inorderTraversal(root.right, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        ans = None\n",
    "\n",
    "        while root:\n",
    "            if root.val > p.val:\n",
    "                ans = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        def f(root, p):\n",
    "            if not root:\n",
    "                return root\n",
    "            ret = f(root.left, p)\n",
    "            if ret:\n",
    "                return ret\n",
    "            return root if root.val > p.val else f(root.right, p)\n",
    "        return f(root, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        stack = []\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            if root == p:\n",
    "                if not root.right:\n",
    "                    if not stack:   return None\n",
    "                    else:   return stack[-1]\n",
    "                else:\n",
    "                    root = root.right\n",
    "                    while root.left:\n",
    "                        root = root.left\n",
    "                    return root\n",
    "            root = root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        \n",
    "        def dfs(root, prev):\n",
    "            if root is None:\n",
    "                return prev\n",
    "\n",
    "            if root.val > p.val:\n",
    "                return dfs(root.left, root)\n",
    "            elif root.val < p.val:\n",
    "                return dfs(root.right, prev)\n",
    "            # 找到 target\n",
    "\n",
    "            if p.right is None:\n",
    "                return prev\n",
    "\n",
    "            res = p.right\n",
    "            while res.left is not None:\n",
    "                res = res.left\n",
    "            return res\n",
    "        return dfs(root, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        target = None\n",
    "        # 如果有右子树\n",
    "        if p.right is not None:\n",
    "            target = p.right\n",
    "            while target.left is not None:\n",
    "                target = target.left\n",
    "            return target\n",
    "\n",
    "        # 没有右子树，根据二叉搜索树的性质找到p节点，在遇到比其大的节点时更新后继节点\n",
    "        cur = root\n",
    "        while cur != p:\n",
    "            if cur.val > p.val:\n",
    "                target = cur\n",
    "                cur = cur.left  # 尝试找到比p大的且更小的节点\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return target\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        st, pre, cur = [], None, root\n",
    "        while st or cur:\n",
    "            while cur:\n",
    "                st.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = st.pop()\n",
    "            if pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        def inOrderTraverse(node):\n",
    "            if node:\n",
    "                yield from inOrderTraverse(node.left)\n",
    "                yield node\n",
    "                yield from inOrderTraverse(node.right)\n",
    "        traverse = inOrderTraverse(root)\n",
    "        while True:\n",
    "            curr = next(traverse)\n",
    "            if curr == p:\n",
    "                try:\n",
    "                    return next(traverse)\n",
    "                except StopIteration:\n",
    "                    return None\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if not root or not p:\n",
    "            return None\n",
    "\n",
    "        next = None\n",
    "        cur = root\n",
    "\n",
    "        while cur:\n",
    "            if p.val > cur.val:\n",
    "                cur = cur.right\n",
    "            \n",
    "            elif p.val < cur.val:\n",
    "                next = cur\n",
    "                cur = cur.left\n",
    "\n",
    "            else:\n",
    "                if cur.right:\n",
    "                    next = cur.right\n",
    "                    while next.left:\n",
    "                        next = next.left\n",
    "                \n",
    "                break\n",
    "        return next\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "\n",
    "    #     self.answer = None\n",
    "    #     self.find_p = False\n",
    "    \n",
    "    #     def traverse(root):\n",
    "    #         if not root:\n",
    "    #             return\n",
    "            \n",
    "    #         if self.answer:\n",
    "    #             return\n",
    "            \n",
    "    #         traverse(root.left)\n",
    "\n",
    "    #         if self.find_p and self.answer == None:\n",
    "    #             self.answer = root\n",
    "            \n",
    "    #         if root == p:\n",
    "    #             self.find_p = True\n",
    "\n",
    "    #         traverse(root.right)\n",
    "        \n",
    "    #     traverse(root)\n",
    "    #     return self.answer\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        self.ans = None\n",
    "        self.flag = False\n",
    "        self.p = p\n",
    "        self.traverse(root)\n",
    "                \n",
    "        return self.ans\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return \n",
    "\n",
    "        self.traverse(root.left)\n",
    "        if self.flag:\n",
    "            self.ans = root\n",
    "            self.flag = False\n",
    "            # print(\"aaa\")\n",
    "            return\n",
    "        if root == self.p:\n",
    "            self.flag = True\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        res = None\n",
    "        found = False\n",
    "        def traverse(n, x):\n",
    "            if n is None:\n",
    "                return\n",
    "            nonlocal found, res\n",
    "            traverse(n.left, x)\n",
    "            if found:\n",
    "                res = n if res is None else res\n",
    "                return\n",
    "            if n.val == x:\n",
    "                found = True\n",
    "            traverse(n.right, x)\n",
    "\n",
    "        traverse(root, p.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        ans=None\n",
    "        while root:\n",
    "            if root.val>p.val:\n",
    "                ans=root\n",
    "                root=root.left#尝试收缩上界\n",
    "            else:\n",
    "                root=root.right#尝试扩大下界\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if root:\n",
    "            if root.val>p.val:\n",
    "                return self.inorderSuccessor(root.left,p) or root\n",
    "            return self.inorderSuccessor(root.right,p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        if root.val <= p.val:\n",
    "            return self.inorderSuccessor(root.right, p)\n",
    "        \n",
    "        left = self.inorderSuccessor(root.left, p)\n",
    "        if left:\n",
    "            return left\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        self.ans = None\n",
    "\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                dfs(root.left)\n",
    "                if (self.ans == None and root.val > p.val):\n",
    "                    self.ans = root\n",
    "                dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.inorder = []\n",
    "    \n",
    "    def inorder_traverse(self, root: TreeNode):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inorder_traverse(root.left)\n",
    "        self.inorder.append(root)\n",
    "        self.inorder_traverse(root.right)\n",
    "    \n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        self.inorder_traverse(root)\n",
    "        for i in range(len(self.inorder)):\n",
    "            if self.inorder[i].val == p.val:\n",
    "                return None if i + 1 == len(self.inorder) else self.inorder[i + 1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        pre = None\n",
    "        cur = root\n",
    "        stack = []\n",
    "\n",
    "        while stack or cur:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                if pre is p:\n",
    "                    return cur\n",
    "                pre = cur\n",
    "                cur = cur.right\n",
    "\n",
    "        return None\n",
    "        '''\n",
    "                ans = []\n",
    "        stack = []\n",
    "        cur = root\n",
    "        while stack or cur:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                ans.append(cur.val)\n",
    "                cur = cur.right\n",
    "        return ans\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if root:\n",
    "            if root.val > p.val:\n",
    "                return self.inorderSuccessor(root.left, p) or root\n",
    "            return self.inorderSuccessor(root.right, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        res = TreeNode(float(\"inf\"))\n",
    "        found = None\n",
    "        def dfs(cur_node):\n",
    "            nonlocal found, res\n",
    "            if not cur_node:\n",
    "                return\n",
    "            dfs(cur_node.left)\n",
    "            if cur_node.val == p.val:\n",
    "                found = True\n",
    "            elif found:\n",
    "                if p.val < cur_node.val < res.val:\n",
    "                    res = cur_node\n",
    "            dfs(cur_node.right)\n",
    "        dfs(root)\n",
    "        return res if res.val != float(\"inf\") else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        \n",
    "        ans = []\n",
    "        def inOrder(root): # \n",
    "            idx_root = None\n",
    "            if root is None:\n",
    "                return None\n",
    "            \n",
    "            idx_l = inOrder(root.left)\n",
    "            ans.append(root)\n",
    "            if root == p:\n",
    "                idx_root = len(ans)\n",
    "            idx_r = inOrder(root.right)\n",
    "            # print(root.val, idx_l, idx_root, idx_r)\n",
    "\n",
    "            if idx_l is not None:\n",
    "                return idx_l\n",
    "            elif idx_root is not None:\n",
    "                return idx_root\n",
    "            elif idx_r is not None:\n",
    "                return idx_r\n",
    "            else:\n",
    "                return None\n",
    "            \n",
    "        idx = inOrder(root)\n",
    "        # print(ans)\n",
    "        # print(idx)\n",
    "        if idx is None:\n",
    "            return None\n",
    "        if idx >= len(ans):\n",
    "            return None\n",
    "        return ans[idx]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        node = None\n",
    "        if p.right:\n",
    "            node = p.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        \n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.val > p.val:\n",
    "                node = cur\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        res = TreeNode(float(\"inf\"))\n",
    "        found = None\n",
    "        def dfs(cur_node):\n",
    "            nonlocal found, res\n",
    "            if not cur_node:\n",
    "                return\n",
    "            dfs(cur_node.left)\n",
    "            if cur_node.val == p.val:\n",
    "                found = True\n",
    "            elif found:\n",
    "                if p.val < cur_node.val < res.val:\n",
    "                    res = cur_node\n",
    "            dfs(cur_node.right)\n",
    "        dfs(root)\n",
    "        return res if res.val != float(\"inf\") else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        self.res = None\n",
    "        self.k = 1\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if self.k == 0:\n",
    "                self.k -= 1\n",
    "                self.res = root\n",
    "            if root == p:\n",
    "                self.k -= 1 \n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        self.ans = None\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.right)\n",
    "            if node.val > p.val:\n",
    "                self.ans = node\n",
    "            dfs(node.left)\n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        inorder = self.travel(root)\n",
    "        for i in range(len(inorder)):\n",
    "            if i<len(inorder)-1 and inorder[i].val == p.val:\n",
    "                return inorder[i+1]\n",
    "        return None\n",
    "\n",
    "    def travel(self, node):\n",
    "        if node is None:\n",
    "            return []\n",
    "        return self.travel(node.left) + [node] + self.travel(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        cur = root\n",
    "        res = None\n",
    "        while cur:\n",
    "            if cur.val <= p.val: # <= not <\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                res = cur # cur.val wrong. return treenode\n",
    "                cur = cur.left\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        foundTarget = False\n",
    "\n",
    "        stack = []\n",
    "        cur = root\n",
    "\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "\n",
    "            cur = stack.pop()\n",
    "\n",
    "            if foundTarget:\n",
    "                return cur\n",
    "\n",
    "            else:\n",
    "                if cur == p:\n",
    "                    # Do something\n",
    "                    foundTarget = True\n",
    "\n",
    "                cur = cur.right\n",
    "                \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        res = TreeNode(float(\"inf\"))\n",
    "        found = None\n",
    "        def dfs(cur_node):\n",
    "            nonlocal found, res\n",
    "            if not cur_node:\n",
    "                return\n",
    "            dfs(cur_node.left)\n",
    "            if cur_node.val == p.val:\n",
    "                found = True\n",
    "            elif found:\n",
    "                if p.val < cur_node.val < res.val:\n",
    "                    res = cur_node\n",
    "            dfs(cur_node.right)\n",
    "        dfs(root)\n",
    "        return res if res.val != float(\"inf\") else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        ans = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if root == p or ans:\n",
    "                ans.append(root)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        if len(ans) <= 1:\n",
    "            return \n",
    "        else:\n",
    "            return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        \n",
    "        \n",
    "        def mid_traverse(node):\n",
    "            if node is None:\n",
    "                return []\n",
    "            res = []\n",
    "            res.extend(mid_traverse(node.left))\n",
    "            res.append(node)\n",
    "            res.extend(mid_traverse(node.right))\n",
    "            return res\n",
    "        \n",
    "        node_list = mid_traverse(root)\n",
    "        ##print(node_list)\n",
    "        \n",
    "        for idx, node in enumerate(node_list):\n",
    "            if node == p:\n",
    "                if idx < len(node_list) - 1:\n",
    "                    return node_list[idx +1]\n",
    "        return\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        arr=[]\n",
    "        def kkk(node):\n",
    "            if node:\n",
    "                kkk(node.left)\n",
    "                arr.append(node)\n",
    "                kkk(node.right)\n",
    "        kkk(root)\n",
    "        for node in arr:\n",
    "            if node.val>p.val: return node\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "\n",
    "    #     self.answer = None\n",
    "    #     self.find_p = False\n",
    "    \n",
    "    #     def traverse(root):\n",
    "    #         if not root:\n",
    "    #             return\n",
    "            \n",
    "    #         if self.answer:\n",
    "    #             return\n",
    "            \n",
    "    #         traverse(root.left)\n",
    "\n",
    "    #         if self.find_p and self.answer == None:\n",
    "    #             self.answer = root\n",
    "            \n",
    "    #         if root == p:\n",
    "    #             self.find_p = True\n",
    "\n",
    "    #         traverse(root.right)\n",
    "        \n",
    "    #     traverse(root)\n",
    "    #     return self.answer\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        self.ans = None\n",
    "        self.flag = False\n",
    "        self.p = p\n",
    "        self.traverse(root)\n",
    "                \n",
    "        return self.ans\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return \n",
    "\n",
    "        if self.ans != None:\n",
    "            return\n",
    "\n",
    "        self.traverse(root.left)\n",
    "        \n",
    "        if self.flag:\n",
    "            self.ans = root\n",
    "            self.flag = False\n",
    "            # print(\"aaa\")\n",
    "            return\n",
    "        \n",
    "        if root == self.p:\n",
    "            self.flag = True\n",
    "        \n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        stack = []\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            if root == p:\n",
    "                if not root.right:\n",
    "                    if not stack:   return None\n",
    "                    else:   return stack[-1]\n",
    "                else:\n",
    "                    root = root.right\n",
    "                    while root.left:\n",
    "                        root = root.left\n",
    "                    return root\n",
    "            root = root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root, ans):\n",
    "        if root:\n",
    "            self.dfs(root.left, ans)\n",
    "            ans.append(root)\n",
    "            self.dfs(root.right, ans)\n",
    "    \n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        ans = list()\n",
    "        self.dfs(root, ans)\n",
    "        for i in range(len(ans)):\n",
    "            node = ans[i]\n",
    "            if node.val == p.val:\n",
    "                if i + 1 < len(ans):\n",
    "                    return ans[i + 1]\n",
    "                else:\n",
    "                    return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        arr=[]\n",
    "        def kkk(node):\n",
    "            if node:\n",
    "                kkk(node.left)\n",
    "                arr.append(node)\n",
    "                kkk(node.right)\n",
    "        kkk(root)\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]==p:\n",
    "                if i==len(arr)-1: return None\n",
    "                else: return arr[i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        node_buffer = []\n",
    "        node = root\n",
    "        node_list = []\n",
    "        match_flag = False\n",
    "\n",
    "        while node_buffer or node:\n",
    "            while node:\n",
    "                node_buffer.append(node)\n",
    "                node = node.left\n",
    "            node = node_buffer.pop()\n",
    "            if match_flag:\n",
    "                return node\n",
    "            node_list.append(node)\n",
    "            if node.val == p.val:\n",
    "                match_flag = True\n",
    "\n",
    "            node = node.right\n",
    "        return None\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        successor = None\n",
    "        while root:\n",
    "            if root.val > p.val:\n",
    "                successor = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return successor\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        ans = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if not ans and root.val > p.val:\n",
    "                ans.append(root)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        if not ans:\n",
    "            return\n",
    "        return ans[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        cand = None\n",
    "        def helper(root: TreeNode) -> Optional[TreeNode]:\n",
    "            nonlocal cand\n",
    "            if not root: return\n",
    "            if p.val < root.val:\n",
    "                cand = root\n",
    "                helper(root.left)\n",
    "            else:\n",
    "                helper(root.right)\n",
    "        helper(root)\n",
    "        return cand\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        self.upper = None\n",
    "        self.dfs(root, p)\n",
    "        return self.upper\n",
    "        \n",
    "    def dfs(self, root, p):\n",
    "        if root is None:\n",
    "            return\n",
    "        \n",
    "        if root.val <= p.val:\n",
    "            self.lower = root\n",
    "            self.dfs(root.right, p)\n",
    "        else:\n",
    "            self.upper = root\n",
    "            self.dfs(root.left, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        res = None\n",
    "        def find_succ(node):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val<=p.val:\n",
    "                return find_succ(node.right)\n",
    "            res = node\n",
    "            return find_succ(node.left)\n",
    "\n",
    "        find_succ(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        self.ans = 0\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            res.append(root)\n",
    "            if root == p: self.ans = len(res)#记录下p的下一个节点的index\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        if self.ans == len(res): return None#如果p是最后一个，则返回None\n",
    "        return res[self.ans]   \n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        ans = []\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return dfs(node.left) + [node] + dfs(node.right)\n",
    "        \n",
    "        ans = dfs(root)\n",
    "        ans += [None]\n",
    "        for i in range(len(ans)):\n",
    "            if ans[i].val == p.val:\n",
    "                return ans[i + 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "         # 因为搜索二叉树的性质，我们可以不断缩小搜索范围，迭代性地更新ans的值。\n",
    "        ans = None\n",
    "        while root:\n",
    "            if root.val > p.val:\n",
    "                    ans = root\n",
    "                    root = root.left\n",
    "            else:\n",
    "                # 没找到父亲\n",
    "                root = root.right\n",
    "        return ans \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if root:\n",
    "            if root.val<p.val:\n",
    "                return self.inorderSuccessor(root.right,p)\n",
    "            elif root.val>p.val:\n",
    "                ans=self.inorderSuccessor(root.left,p)\n",
    "                if ans:\n",
    "                    return ans\n",
    "                else:\n",
    "                    return root\n",
    "            else:\n",
    "                #root.val==p:\n",
    "                if root.right:\n",
    "                    cur=root.right\n",
    "                    while cur.left:\n",
    "                        cur=cur.left\n",
    "                    return cur\n",
    "                else:\n",
    "                    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "\n",
    "        node = root\n",
    "        stack = []\n",
    "        flag = 0\n",
    "        while stack or node:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            \n",
    "            node = stack.pop()\n",
    "            if flag:\n",
    "                return node\n",
    "\n",
    "            if node == p:\n",
    "                flag = 1\n",
    "            if node.right:\n",
    "                node = node.right\n",
    "            else:\n",
    "                node = None\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        self.flag = False\n",
    "        self.p = p\n",
    "        self.ans = None\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            if not self.ans and self.flag == True:\n",
    "                self.ans = node\n",
    "            if node == self.p:\n",
    "                self.flag = True\n",
    "            dfs(node.right)\n",
    "            \n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        cand = None\n",
    "        # if p.right exists, search p.right\n",
    "        if p.right:\n",
    "            cand = p.right\n",
    "            while cand.left:\n",
    "                cand = cand.left\n",
    "            return cand\n",
    "        # if p.right doesn't exist, search from root and update cand\n",
    "        while root:\n",
    "            if p.val < root.val:\n",
    "                cand = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return cand\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        cur = root\n",
    "        res = None\n",
    "        while cur:\n",
    "            #p是当前节点的下一个节点，下一个节点肯定是大于，所以用res储存\n",
    "            if cur.val > p.val:\n",
    "                res = cur\n",
    "                cur = cur.left\n",
    "                \n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return res\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
